2023-03-15-1维DP四边形不等式优化(决策单调性优化)

对序列切割问题，令 ，即 到 的最优解

其中 表示 到 作为一段的代价

若对所有 有 (四边形不等式)，即可使用此优化 (所以叫四边形不等式优化)

这是因为若四边形不等式满足，则

大大小小

于是如果 大小

那对于所有 有 大小 (*)

(*)就是强化版决策单调性

令 表示 的决策

那么 不降就是普通的决策单调性(**)，它可以由(*)得出

用 合并 数组中一段相同的值，并用队列维护

求出后就从右到左看它能更新哪些 ，如果能整个更新，就把这块丢掉，否则就在第一个不能整块更新的块里二分，正确性由(*)和(**)保证

struct Info {
    int l, r, pre;
} q[N];

struct Opt {
    ll val, pre;
} f[N];

ll F(int j, int i) {
    // 具体问题具体分析
}

int search(Info x, int i) {
    int l = x.l;
    int r = x.r;
    int ans = r + 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (F(i, mid) <= F(x.pre, mid)) {
            ans = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    return ans;
}

void DP() {
    q[1] = (Info){1, n, 0};
    int l = 1, r = 2;
    for (int i = 1; i <= n; i++) {
        while (q[l].r < i) l++;
        int j = q[l].pre;
        f[i] = (Opt){F(j, i), j};
        q[l].l = i + 1;
        if (q[l].r == i) l++;
        while (l < r && F(i, q[r-1].l) <= F(q[r-1].pre, q[r-1].l)) r--;
        int pos = i + 1;
        if (l < r) {
            pos = search(q[r-1], i);
            q[r-1].r = pos - 1;
        }
        if (pos > n) continue;
        q[r++] = (Info){pos, n, i};
    }
    printf("%lld\n", f[n].val);
}
Copy